import java.util.ArrayList;
import java.util.List;

public class Greedy {
    final int N;
    final int start;//出发点
    int[][] D;//用于存储两个城市之间的距离
    boolean[] done;//用于存储已访问过的城市
    List<Integer> steps=new ArrayList<>();

    /*
    * 贪心算法解决TSP问题
    * 输入为：距离矩阵，城市个数，出发点。
    */
    public Greedy(int D[][],int N,int start){
        done = new boolean[N];
        this.start=start;
        this.D=D;
        this.N=N;
    }
    /*
     * 找距离start最近的点。
     */
    int getMinD(int nowStep){
        if (steps.size()==N) return start;//看是不是走到最后一个点了
        int nextStep=-1;
        int min=Integer.MAX_VALUE;//初始化设置为极大
        for (int i=0;i<N;++i){
            if (nowStep==i) continue;//排除自己到自己
            else if (done[i]) continue;//排除已经走过的
            if (D[nowStep][i]<min){
                min=D[nowStep][i];
                nextStep=i;
            }
        }
        return nextStep;
    }
    public List<Integer> run(){
        int step=start;//从0出发！
        while (steps.size()<N){
            done[step]=true;//标记足迹
            steps.add(step);//记录足迹
            int nextStep=getMinD(step);//获取下一步最小代价的
            if (nextStep==-1){//所有的都找了（本题不会出现这种情况！）
                System.out.println("没找着哦！");
                return null;
            }else{
                step=nextStep;//走入下一步
            }
        }
//        showSteps();//打印输出结果
        return steps;
    }
    public void showSteps(){
        int last=start;
        int sum=0;
        System.out.println("出发地\t---[距离]--->\t到达地");
        for (int step:steps){
            if (last==step) continue;
            System.out.println("  "+last+"\t\t----["+D[last][step]+"]---->\t  "+step);
            sum+=D[last][step];
            last=step;
        }

        sum+=D[last][start];
        System.out.println("  "+last+"\t\t----["+D[last][start]+"]---->\t  "+start);
        System.out.println("总路径距离："+sum);
    }

}
